package leetcode._06_回溯;

import org.junit.Test;
import java.util.*;

/**
 * @author pppppp
 * @date 2022/3/8 8:32
 */
public class _51_N皇后 {
    /*3.官方题解 快速判断是否处于同一行列或者斜线*/
    @Test
    public void T_3() {
        for (int i = 1; i <= 5; i++) {
            List<List<String>> lists = solveNQueens3(i);
            System.out.println();
        }
        System.out.println();
    }

    private List<List<String>> solveNQueens3(int n) {
        boolean []row = new boolean[n];
        boolean []col = new boolean[n];
        boolean []lx = new boolean[2*n + 1];
        boolean []rx = new boolean[2*n + 1];
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < n; j++) {
            sb.append(".");
        }
        String []basic = new String[n];
        for (int j = 0; j < n; j++) {
            StringBuilder t = new StringBuilder(sb);
            t.setCharAt(j,'Q');
            basic[j] = new String(t);
        }
        dfs3(0,n,row,col,lx,rx,basic);
        return res;
    }

    private void dfs3(int pos, int n,boolean[] row, boolean[] col, boolean[] lx, boolean[] rx,String []basic) {
        if(pos == n){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!row[pos] && !col[i] && !lx[pos-i+n] && !rx[pos+i]){
                path.add(basic[i]);
                row[pos] = col[i] = lx[pos-i + n] = rx[pos+i] = true;
                dfs3(pos+1,n,row,col,lx,rx,basic);
                row[pos] = col[i] = lx[pos-i + n] = rx[pos+i] = false;
                path.remove(path.size()-1);
            }
        }
    }


    /*2.使用回溯*/
    @Test
    public void T_2() {
        List<List<String>> lists = solveNQueens2(8);
        System.out.println();
    }

    List<List<String>> res = new ArrayList<>();
    ArrayList<String> path = new ArrayList<>();

    public List<List<String>> solveNQueens2(int n) {
        if (n < 4) {
            if (n == 1) {
                List<String> t = new ArrayList<>();
                t.add("Q");
                res.add(t);
            }
            return res;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(".");
        }
        String basic = new String(sb);
        boolean[][] arrived = new boolean[n][n];
        int[] arrivedNum = new int[n];
        dfs(0, 0, n, basic, arrived, arrivedNum);
        return res;
    }

    /*将i，j能到达的位置全部置true*/
    private void dfs(int i, int j, int n, String basic, boolean[][] arrived, int[] arrivedNum) {

        if (i == n) {
            res.add(new ArrayList<>(path));
            return;
        }

        if (arrivedNum[i] >= n) {
            return;
        }
        for (int k = j; k < n; k++) {
            while (k < n && arrived[i][k]) {
                k++;
            }
            if (k == n) {
                return;
            }
            StringBuilder sb = new StringBuilder(basic);
            sb.setCharAt(k, 'Q');
            path.add(new String(sb));

            boolean[][] arrived_copy = new boolean[n][n];
            for (int i1 = 0; i1 < n; i1++) {
                arrived_copy[i1] = Arrays.copyOf(arrived[i1], n);
            }
            int[] arrivedNum_copy = Arrays.copyOf(arrivedNum, n);

            /*清除i，j的横竖斜*/
            clearLine(i, k, n, arrived_copy, arrivedNum_copy);

            /*递归下一行*/
            dfs(i + 1, 0, n, basic, arrived_copy, arrivedNum_copy);

            path.remove(path.size() - 1);
        }
    }


    private void clearLine(int i, int j, int n, boolean[][] arrived, int[] arrivedNum) {
        /*将行clear*/
        for (int k = j; k < n; k++) {
            if (!arrived[i][k]) {
                arrived[i][k] = true;
                arrivedNum[i]++;
            }
        }
        /*将列clear 列都+1了，减去重复+1*/
        for (int k = i + 1; k < n; k++) {
            if (!arrived[k][j]) {
                arrived[k][j] = true;
                arrivedNum[k]++;
            }
        }

        int i1 = i + 1, j1 = j + 1;
        i++;
        j--;
        /*左下置true*/
        while (i < n && j >= 0) {
            if (!arrived[i][j]) {
                arrivedNum[i]++;
                arrived[i][j] = true;
            }
            i++;
            j--;
        }
        /*右下置true*/
        while (i1 < n && j1 < n) {
            if (!arrived[i1][j1]) {
                arrived[i1][j1] = true;
                arrivedNum[i1]++;
            }
            i1++;
            j1++;
        }
    }

    /*1.直接递推有漏检的情况*/
    @Test
    public void T_() {
        List<List<String>> lists = solveNQueens(5);
        for (int i = 0; i < lists.size(); i++) {
            System.out.println(i + 1);
            List<String> strings = lists.get(i);
            for (String string : strings) {
                System.out.println(string);
            }
            System.out.println();
        }
        System.out.println();
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if (n < 4) {
            if (n == 1) {
                List<String> t = new ArrayList<>();
                t.add("Q");
                res.add(t);
            }
            return res;
        }
        List<String> q41 = Arrays.asList(".Q..", "...Q", "Q...", "..Q.");
        List<String> q42 = Arrays.asList("..Q.", "Q...", "...Q", ".Q..");
        Queue<List<String>> queue = new LinkedList<>();
        queue.add(q41);
        queue.add(q42);
        while (n > 4) {
            int size = queue.size();
            while (size > 0) {
                List<String> poll = queue.poll();
                List<List<String>> n1 = to4Direct(poll);
                for (List<String> list : n1) {
                    queue.add(list);
                }

                size--;
            }
            n--;
        }
        return new ArrayList<>(queue);
    }

    private List<List<String>> to4Direct(List<String> solution) {
        int length = solution.get(0).length();
        /*左上角*/
        List<String> l1 = new ArrayList<>();
        List<String> l2 = new ArrayList<>();
        List<String> l3 = new ArrayList<>();
        List<String> l4 = new ArrayList<>();
        List<List<String>> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append(".");
        }

        l1.add("Q" + new String(sb));
        l2.add("Q" + new String(sb));
        l3.add(new String(sb) + "Q");
        l4.add(new String(sb) + "Q");
        for (int i = 0; i < length; i++) {
            String s = solution.get(i);
            l1.add("." + s);
            l2.add(0, "." + s);
            l3.add(s + ".");
            l4.add(0, s + ".");
        }
        res.add(l1);
        res.add(l2);
        res.add(l3);
        res.add(l4);

        return res;
    }
}

